package solution.misc;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class QuickStack<T extends Comparable<T>> {
	class Node {
		T data;
		Node next;
	}

	Node head = null;

	T minT = null;

	T min() {
		if (head == null)
			return null;

		T value = head.data;
		for (Node p = head.next; p != null; p = p.next) {
			if (value.compareTo(p.data) > 0) {
				value = p.data;
			}
		}
		return value;
	}

	T pop() {
		if (head == null) {
			minT = null;
			return null;
		}
		T data = head.data;
		if (data.compareTo(minT) == 0) {
			// recompute minT
		}

		head = head.next;
		return data;
	}

	void push(T data) {
		Node nd = new Node();
		nd.data = data;
		if (head == null) {
			head = nd;
			minT = data;
			return;
		}

		if (minT.compareTo(data) > 0) {
			minT = data;
		}
		nd.next = head;
		head = nd;
	}

	T top() {
		if (head == null)
			return null;
		return head.data;
	}

	@Test
	public void z_test() {
		QuickStack<Integer> qs = new QuickStack<Integer>();
		qs.push(1);
		Assert.assertEquals((Integer) 1, qs.min());
		Assert.assertEquals((Integer) 1, qs.top());
		qs.push(2);
		Assert.assertEquals((Integer) 1, qs.min());
		Assert.assertEquals((Integer) 2, qs.top());
		Assert.assertEquals((Integer) 2, qs.pop());
		Assert.assertEquals((Integer) 1, qs.pop());
		Assert.assertEquals(null, qs.min());
	}

}
